package monotonestack;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Classname : MaximalRectangle
 * @Description : 85. 最大矩形
 * https://leetcode.cn/problems/maximal-rectangle/
 * @Author : cty
 * @Date 2023/3/27 21:52
 */


public class MaximalRectangle {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        int max = 0, m = matrix.length, n = matrix[0].length;
        int[][] mat = new int[m][n];

        // 将字符数组转化为数字数组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = matrix[i][j] - '0';
            }
        }

        // 将每一列转换成一个柱状图，柱状图的高度为从当前位置向上连续1的个数
        for (int j = 0; j < n; j++) {
            for (int i = 1; i < m; i++) {
                if (mat[i][j] == 1) {
                    mat[i][j] += mat[i - 1][j];
                }
            }
        }

        // 遍历每个柱状图的最大面积，取最大值
        for (int i = 0; i < m; i++) {
            max = Math.max(max, getMaxArea(mat[i]));
        }
        return max;
    }

    // 获取柱状图的最大面积
    private int getMaxArea(int[] heights) {
        int max = 0, n = heights.length;
        Stack<Integer> stack = new Stack<>();
        int[][] bounds = new int[2][n];
        Arrays.fill(bounds[0], -1);
        Arrays.fill(bounds[1], n);

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                bounds[1][stack.pop()] = i;
            }
            if (!stack.isEmpty()) {
                bounds[0][i] = stack.peek();
            }
            stack.push(i);
        }

        for (int i = 0; i < n; i++) {
            max = Math.max(max, heights[i] * (bounds[1][i] - bounds[0][i] - 1));
        }
        return max;
    }
}
